package leetcode;

import java.util.*;

public class MyCalendar {

//    TreeSet实现
    TreeSet<int[]> set;

    public MyCalendar() {
        set = new TreeSet<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] <= o2[0]) // o1在左边
                    return -1;
                else if (o1[0] >= o2[1]) // o1在右边，o1大
                    return 1;
                else return 0; //如果有交叉，则认为是一样的，插入set会失败
            }
        });
    }

    public boolean book(int startTime, int endTime) {
        return set.add(new int[]{startTime, endTime});
    }








//    二分查找实现
//    private ArrayList<int[]> time;
//
//    public MyCalendar() {
//        time = new ArrayList<>();
//    }
//
//    public boolean book(int startTime, int endTime) {
//
//        Collections.sort(time, (int[] t1, int[] t2) -> {
//            return t1[0] - t2[0];
//        });
//        if (time.size() == 0 || canBook(startTime, endTime, 0, time.size() - 1)) {
//            time.add(new int[]{startTime, endTime});
//            return true;
//        }
//        return false;
//    }
//
//    private boolean canBook(int startTime, int endTime, int l, int r) {
//        if ( l > r) return false;
//        if (l == r) {
//            if (time.get(l)[0] >= endTime || time.get(l)[1] <= startTime)
//                return true;
//            return false;
//        }
//        int mid = (l + r) / 2;
//        //判断mid左边能否安排
//        if (time.get(mid)[0] >= endTime) {
//            if (mid == 0) return true;
//            if (time.get(mid - 1)[1] <= startTime)
//                return true;
//            if (canBook(startTime, endTime, l, mid - 1)) {
//                return true;
//            }
//            return false;
//        }
//        //判断右边
//        if (time.get(mid)[1] <= startTime) {
//            if (mid == time.size() - 1)
//                return true;
//            if (time.get(mid + 1)[0] >= endTime)
//                return true;
//            if (canBook(startTime, endTime, mid + 1, r)) {
//                return true;
//            }
//            return false;
//        }
//        return false;
//    }





}
